/*
题目: 二叉搜索子树的最大键值和
给你一棵以 root 为根的 二叉树 ，请你返回 任意 二叉搜索子树的最大键值和。

二叉搜索树的定义如下：

    任意节点的左子树中的键值都 小于 此节点的键值。
    任意节点的右子树中的键值都 大于 此节点的键值。
    任意节点的左子树和右子树都是二叉搜索树。

https://leetcode.cn/problems/maximum-sum-bst-in-binary-tree
 */
public class MaxSumBST {
    final int INF = -1000000007;
    int src = 0;

    public int maxSumBST(TreeNode root) {
        DFS(root);
        return src;
    }

    private int[] DFS(TreeNode root) {
        if (root == null)   return new int[] {0, 0, 0}; // 这个返回值没有什么作用
        int[] leftRet = DFS(root.left);
        int[] rightRet = DFS(root.right);

        // 如果没有孩子结点
        if (root.left == null && root.right == null) {
            src = Math.max(src, root.val);
            return new int[] {root.val, root.val, root.val};
        } else if (root.left != null && root.right != null) {
            if (leftRet[0] != INF && rightRet[0] != INF &&
                    root.left.val < root.val && root.right.val > root.val && leftRet[2] < root.val && rightRet[1] > root.val) {

                int input = leftRet[0] + root.val + rightRet[0];
                src = Math.max(src, input);
                return new int[] {input, leftRet[1], rightRet[2]};
            } else {
                return new int[] {INF, 0, 0};
            }
        } else if (root.left != null) { // 只有左孩子
            if (leftRet[0] != INF && leftRet[2] < root.val) {
                int input = leftRet[0] + root.val;
                src = Math.max(src, input);
                return new int[] {input, leftRet[1], root.val};
            } else {
                return new int[] {INF, 0, 0};
            }
        } else { // 只有右孩子
            if (rightRet[0] != INF && rightRet[1] > root.val) {
                int input = rightRet[0] + root.val;
                src = Math.max(src, input);
                return new int[] {input, root.val, rightRet[2]};
            } else {
                return new int[] {INF, 0, 0};
            }
        }
    }

    // -------------------------------------------------------------------------------------------------
    // 标记所有的 二叉搜索树, 不是 BST, Value 为 Pair, 分别记录总和, 最小值, 最大值, 不是 BST 则为 Null
    Map<TreeNode, Pair> map = new HashMap<> ();
    int src = 0;

    public static class Pair {
        int sum, min, max;
        public Pair(int sum, int min, int max) {
            this.sum = sum;
            this.min = min;
            this.max = max;
        }
    }

    public int maxSumBST1(TreeNode root) {
        DFS(root);
        return src;
    }

    private void DFS1(TreeNode root) {
        if (root == null)   return ;

        DFS1(root.left);
        DFS1(root.right);

        if (root.left == null && root.right == null) { // 叶子结点
            map.put(root, new Pair(root.val, root.val, root.val));
            src = Math.max(src, root.val);
        } else if (root.left != null && root.right != null) {
            Pair leftTree = map.get(root.left);
            Pair rightTree = map.get(root.right);
            // 左子树都要小于 root, 右子树都要大于 root
            if (leftTree != null && rightTree != null && root.left.val < root.val && root.right.val > root.val
                    && leftTree.max < root.val && rightTree.min > root.val) {

                int input = root.val + leftTree.sum + rightTree.sum;
                map.put(root, new Pair(input, leftTree.min, rightTree.max));
                src = Math.max(src, input);
            } else {
                map.put(root, null);
            }
        } else if (root.left == null) {
            // 柚子树是 BST, 现在也是 BST
            Pair cur = map.get(root.right);
            if (cur != null && root.right.val > root.val && cur.min > root.val) {
                int input = root.val + cur.sum;
                map.put(root, new Pair(input, root.val, cur.max));
                src = Math.max(src, input);
            } else { // 其中一个条件不满足
                map.put(root, null);
            }
        } else { // root.right == null, 只有左子树
            Pair cur = map.get(root.left);
            if (cur != null && root.left.val < root.val && cur.max < root.val) {
                int input = root.val + cur.sum;
                map.put(root, new Pair(input, cur.min, root.val));
                src = Math.max(src, input);
            } else {
                map.put(root, null);
            }
        }
    }
}
